package Exercise;

import java.util.Arrays;

/**
 * Description：
 * Author: zhangc
 * Date：2017/8/17 19:06
 */
public class HeapSort {


    public static <T extends Comparable<? super T>> void heapSort(T[] array) {
        adjustHead(array, (array.length >> 1) - 1);
        for (int i = array.length - 1; i >= 0; i--) {
            swap(array, 0, i);
            adjustOne(array, i, 0);
        }
    }

    // 调整一次堆
    private static <T extends Comparable<? super T>> void adjustHead(T[] array, int index) {
        for (int i = index; i >= 0; i--) {
            adjustOne(array, array.length, i);
        }
    }

    // 调整一个元素
    private static <T extends Comparable<? super T>> void adjustOne(T[] array, int size, int index) {
        int left = 2 * index + 1, right = 2 * index + 2, max;
        if (left < size && right < size) {
            max = max(array, left, right);
            if (array[ max ].compareTo(array[ index ]) > 0) {
                swap(array, index, max);
                adjustOne(array, size, max);
            }
        } else if (left < size) {
            if (array[ left ].compareTo(array[ index ]) > 0) {
                swap(array, left, index);
                adjustOne(array, size, left);
            }
        } else if (right < size) {
            if (array[ right ].compareTo(array[ index ]) > 0) {
                swap(array, right, index);
                adjustOne(array, size, right);
            }
        }
    }

    public static <T extends Comparable<? super T>> int max(T[] array, int l, int r) {
        return array[ l ].compareTo(array[ r ]) > 0 ? l : r;
    }

    //交换元素
    public static <T extends Comparable<? super T>> void swap(T[] array, int l, int r) {
        T temp;
        temp = array[ r ];
        array[ r ] = array[ l ];
        array[ l ] = temp;
    }

    public static void main(String[] args) {
        Integer[] ints = {1, 44, 567, 34, 33322, 2990, 876, 3, 2, 5, 8, 6, 9, 3, 8, 22, 11, 22, 11, 222, 2};
        heapSort(ints);
        System.out.println(Arrays.toString(ints));
    }

}
